/*
 * @lc app=leetcode id=480 lang=cpp
 *
 * [480] Sliding Window Median
 */

// @lc code=start
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        K = k;
        s1.clear();
        s2.clear();
        if (k == 1) {
            vector<double> ans;
            for (auto n : nums) {
                ans.push_back(n);
            }
            return ans;
        } else if (k==2) {
            vector<double> ans;
            for (int i = 1; i < nums.size(); ++i) {
                ans.push_back((static_cast<double>(nums[i-1]) + static_cast<double>(nums[i]) )/ 2.0);
            }
            return ans;
        }
        int n = (k + 1) / 2;
        for (int i = 0; i < k; ++i) {
            if (s1.size() == n) {
                auto t = *s1.begin();
                if (t > nums[i]){
                    s1.insert(nums[i]);
                    s1.erase(s1.begin());
                    s2.insert(t);                    
                } else {
                    s2.insert(nums[i]);
                }
            } else {
                s1.insert(nums[i]);
            }
        }
        vector<double> ans;
        ans.push_back(Median());
        int  m = nums.size();
        for (int i = k; i < m; ++i)  {
             Pop(nums[i-k]);          
             Push(nums[i]);   
             ans.push_back(Median());
        }
        return ans;
    }

    void Pop(int k) {
        int t = *(s1.begin());
        if (k > t) {
            auto iter = s2.find(k);
            s2.erase(iter);
        } else {
            auto iter = s1.find(k);
            s1.erase(iter);
            s1.insert(*(s2.begin()));
            s2.erase(s2.begin());
        }
    }
    void Push(int k) {
        int t = *(s1.begin());
        if (k >= t) {
            s2.insert(k);
        } else {
            s1.insert(k);
            s1.erase(s1.begin());            
            s2.insert(t);
        }
    }

    double Median() {
        if (K & 1) {
            return *(s1.begin());
        } else {
            double a = static_cast<double>(*(s1.begin()));
            double b =  static_cast<double>(*(s2.begin()));
            return (a + b)/ 2.0;
        }
    }


    int K;
    std::multiset<int, std::greater<int>> s1;
    std::multiset<int> s2; 
};
// @lc code=end

